package 二分算法;

import java.util.Arrays;

class Solution {
    public int countElements(int[] nums, int k) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);//首先，二分算法是用于有序数组的查找指定元素的算法，它依赖了有序的特性，找某个特定的点
        // 比如 1，2，3，4，5，6，7，8，9，10，11，12，13  我要找数字5 ，在数据量不大的情况下，我们直接无脑for循环就ok了，但是，我们进化了，不在是野蛮人了，
        // 我们要找数字5，因为数组元素是有序的，所以，我们按照二分的思想，直接找数组中间的元素，7，用7和5做比较，如果，比目标值大
        //说明，目标值在这个元素的左侧，如果比目标值小，则说明，目标值在右侧，然后，在在当前的区间，在找这个区间的中间值，和目标值做比较，如此往复，就可以得到要找到的值了
        //像上面的例子，找到7 > 5 ,然后找左侧区间，找到 4 < 5 ,然后找4右边的区间就可以找到5了，我们只需要 3 次就可以找到目标值，但是用for循环我们最少要找5次
        int n = nums.length;//数组长度
        int count = 0;//
        
        for (int x : nums) {
            // 在 sorted 中找第一个大于 x 的位置 (upper bound)
            int lo = 0, hi = n;//左指针和有指针，用来确定二分区间的
            while (lo < hi) {//
                int mid = lo + (hi - lo) / 2;//更新指针，lo + (hi - lo) / 2这个就是当前区间的中间的下标
                if (sorted[mid] <= x) {
                    lo = mid + 1;//如果<目标值，说明，目标值比当前元素大，然后，我们得更新左指针
                } else {
                    hi = mid;//如果>目标值，说明目标值在当前元素的左侧，我们的右指针得更新到当前的mid下标上面
                }
            }
            int greaterCount = n - lo;//得到个严格大于当前元素的个数，看是否满足条件
            if (greaterCount >= k) {
                count++;
            }
        }
        
        return count;
    }}